package sol.leetcode;

/**
 * Longest Increasing Subsequence
 */
public class Issue300 {

    //存放以第i个元素结尾的最长递增序列长度
    int[] lis;
    int max=1;

    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;

        lis = new int[nums.length];
        LIS(nums, nums.length - 1);

        return max;
    }

    //到end位置的前面元素的LIS长度
    public int LIS(int[] nums, int end) {
        if (end == 0) return 1;

        int localMax = 1;
        for (int i = 0; i < end; ++i) {
            int subMax;
            if (lis[i] != 0) subMax = lis[i];
            else {
                subMax = LIS(nums, i);
                lis[i] = subMax;
            }

            if (nums[end] > nums[i] && subMax + 1 > localMax)
                localMax = subMax + 1;
        }
        lis[end] = localMax;

        if (localMax > max) max = localMax;
        return localMax;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 6, 7, 9, 4, 10, 5, 6};
        Issue300 sol = new Issue300();
        System.out.println(sol.lengthOfLIS(nums));
    }
}
